package main.java.indi.zyj.coderecord;

import java.io.StringReader;
import java.util.*;

public class FindItinerary {

    List<String> res = new LinkedList<>();
    Map<String, PriorityQueue<String>> map;
    public List<String> findItinerary(List<List<String>> tickets) {
        map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            if (!map.containsKey(from)) {
                PriorityQueue<String> priorityQueue = new PriorityQueue<>();
                map.put(from, priorityQueue);
            }
            map.get(from).offer(to);
        }
        dfs("JFK");
        Collections.reverse(res);
        return res;
    }

    public void dfs(String from) {
        while (map.containsKey(from) && map.get(from).size() > 0) {
            String to = map.get(from).poll();
            dfs(to);
        }
        res.add(from);
    }

}
